1. Field of the Invention
The present invention relates generally to methods and apparatus for providing a matrix of uniquely addressable locations and, more particularly, to devices that may uniquely address locations in a matrix of addressable locations using a reduced number of address bits.
2. Related Art
Several types of devices require unique locations to be addressed. Examples of these include, but are not limited to, devices that present data such as video displays, devices that may receive and record matrix data such as imaging arrays, and devices that may interconnect internally such as logic arrays. Another type of device which requires unique locations to be addressed is a device which may store and receive data such as a computer memory.
In the context of computer memories, since the advent of the first computer, it has been realized that memory devices for storing information are an essential element of a working computer. Many types of memories for computers have been developed, such as read-only memories (ROMs) and random-access memories (RAMs) as well as magnetic and optical data storage disks. These memories are accessed for read/write operations by the central processing unit (CPU) of the computer.
As computers have gotten smaller and faster, computer and memory unit designers have recognized that the memory devices likewise need to be smaller and operate faster. This has led to very competitive research and development of smaller, faster memory units.
The same has been true of display screens and other devices that may require unique locations to be addressed in order to control their operation. That is, almost all devices of present day that require unique addressing are getting smaller and faster and the trend is continuing.
The basic structure upon which present devices where unique addressing is required (e.g., computer memories, sensor arrays and LCD displays) is based is the row/column array configuration. This structure has been very useful, not only in the field of computer memories but also as a model for conceptually dealing with data structures in the computer science art.
FIG. 1 is an example of a prior art row/column array 1 used to address a unique location. The array 1 includes several rows 2 and columns 3. In some instances, an active component, such as a memory cell, a “pixel” for a display screen or a sensor, may be located at the intersection point of a row and a column.
In order to access a particular element in the array 1, the CPU (not shown) must access both the row and the column corresponding to the location of the element in the array. This entails sending a location address from the CPU to the array 1. The address is then decoded by conventional means such as a multiplexer, and the correct active component may be accessed. Thus, the location of each element may be represented as Nr,c where the r and c represent the row and column, respectively (with the first row and column being denoted as “0” as is conventional).
For example, in the 8×8 array 1 of FIG. 1, if the CPU desired access to the element at the intersection of the third row and the eighth column (n2,7) the CPU would have to send a binary row address of 010 to the row decoder 4 and a binary column address of 111 to the column decoder 5. The row decoder 4 and column decoder 5 are typically implemented as multiplexers. The row decoder 4 converts the three bit row input to a binary representation of 00000100. This output is then transferred to the array 1 through hard wired connections between the output of the row decoder 4 and the array 1. Thus, in order to access each row of the 8×8 array 1, eight physical line connections (as well as the requisite multiplexer) must be included with the array 1. Similarly, the column decoder 5 receives the address 111 and converts it to 10000000 leading to an additional 8 lines (and a second multiplexer) to be connected to the array 1. Thus, a total of 16 physical line connections and two decoders are required in order to access each and every cell of the 8×8 array 1. The interconnections and decoders require space on an integrated chip and therefore serve as a bottleneck when trying to reduce the physical size occupied by the array 1 and its supporting hardware.
When an array is configured in the manner described above, the number of address bits required to access the particular matrix is determined by the size of the array. For example, addressing for a 64 cell, 8×8 matrix 1 requires at least 6 bits, 3 for the row and 3 for the column. Thus, an inherent relationship exists in essentially all conventional array type devices between the requisite number of address bits and the number of active elements in the array 1 as shown in equation (1):addresses=2n  (1)where n is the number of address bits. However, this equation is deceiving; it represents the number of bits the CPU must “send out” in order to access a particular active element of the array 1. In actuality, the number of address bits received by the array 1 is equal to the number of physical line connections to the array 1 as discussed above. Thus, for the 8×8 array discussed above, the array 1 actually receives 16 address bits. This is more than double the number of address bits needed to represent each of the active elements of the array. The transmission of these extra bits requires additional wiring and thus, increases the size and complexity of arrays.
Thus, for a square array containing 2n active elements, 2×2n/2 lines (i.e., 2n/2 columns and 2n/2 rows) must be supplied to and embedded within the array. For example, for an array of 4096 bits (i.e. 212), 128 (i.e., 2×26) lines are necessary, even though the lower limit of binary addresses required from the CPU is only 12—a full order of magnitude less than the row/column scheme requires. This disparity grows exponentially as the array grows in size.
Other issues related to the amount of wiring required in conventional devices include the complex topology necessitated by the perpendicular passage of row and column lines past one another to reach their respective connections to the cell.
Devices having a plurality of uniquely addressable locations of the prior art were typically rigid integrated chips. At times, when repairing or modifying the internal configuration of the product that includes such devices, an integrated chip could be cracked or broken. Further, having the device placed on an integrated chip severely limited the shape the device could take. For example, an array configured in the row/column manner somewhat predisposes the chips to take on a square shape (See e.g., FIG. 1). While the rows and columns may intersect one another at angles other than right angles, the space constraints of the active element which actually stores, displays or receives the information of interest must fit and be connectable to the rows and columns and this limits the row/column configuration.
In addition, there is a lower size limit dictated by the total perimeter necessary to accommodate all interconnections from all lines of the array to external devices. For example, with the 4096 bit array described above, the total perimeter is equal to roughly 128×P, where P is the so called “pitch distance” required between bonding pads. Thus one side of the square array is approximately (128×P/4) in length and the area of the array can be no less than (128×P/4)2. Since bonding pads must be large enough to accommodate ordinary wires, P is a number which cannot be reduced into the microscopic range. Therefore, even if the array itself is reduced to a minuscule area, the overall package cannot be reduced beyond the size dictated by the lower limits of perimeter length. In actuality, the perimeter is even greater than described above since additional grounding lines must be regularly interspersed amongst the signal lines to control inter-line capacitive interference.
The typical row/column configuration may also have inherent signal propagation delays because a signal must traverse the long narrow conduction pathways established in the array before it is read out.
Another source of delay may come in the form of a stabilization timing delay which is inherent in a conventional row/column accessing scheme. Typically, to access, for example, a particular memory cell, sensor or display element, the column is addressed, allowed to stabilize, and then the row is addressed and allowed to stabilize. The timing of the stabilization has received a great deal of attention as it is related to clock cycles with various conventional schemes.